In a data communications network, networking equipment is relied upon to extract and interpret certain fields of data packets transferred among entities of the network. To facilitate the transmission of data packets over the network, layer 2 or layer 3 processing elements, such as routers, Ethernet switches and ATM switches utilize networking equipment to read and interpret the header fields of each data packet that it receives before forwarding the data packet to a proper destination. In particular, every data packet handled by networking equipment at ISO layer 2 or higher of the router requires that certain fields be extracted from the header of the data packet.
The data packet headers typically comprise many fields, some of which need not be read when performing certain functions on the data packet. For example, it may only be necessary to read the header field containing the destination address of the packet when transmitting the data packet over the network. A router addresses this problem by field extraction, or parsing, where only the header fields that are necessary for a particular application are extracted. In one approach to this problem, the router is programmed (in software) by conventional shift and mask techniques to extract the desired fields of the header. Because the header comprises many fields having various sizes and locations, it is clear that standards play an important role for defining the fields so that they can be read or extracted with knowledge as to their content.
An example for extracting fields by the conventional shift and mask technique will be described with reference to FIG. 1 and the following software instructions:
1) READ Location 2--Reg1 PA1 2) AND Reg1, 0xFF--Reg2 PA1 3) AND Reg1, 0xF00--Reg3 PA1 4) SHIFT Reg3 Left 8 PA1 5) SHIFT Reg1 Left 12--Reg4
In FIG. 1, an exemplary header for a data packet with generic header fields labeled A, B, C, D, E, F, G and H is illustrated. Field A has a length of 32 bits, field B has a length of 8 bits, fields C and D are 4 bits in length, field E is 16 bits in length, field F is 3 bits in length, field G is 4 bits in length, and field H has a length of 1 bit. To extract fields B, C, and D, the location defined by address 2 is read and loaded into register 1 at instruction 1. The bits corresponding to the C and D fields are then masked by the AND instruction 2 so that only the bits corresponding to the B field remain in register 2. Thus, the contents of field B have been extracted and placed in the positions corresponding to the least significant bits of register 2.
Next, the bits corresponding to fields B and D are masked by instruction 3 so that only the bits corresponding to the C field are accessible. Then, register 3 is shifted (SHIFT) 8 bits to the left so that the extracted bits corresponding to the C field are placed at the beginning of register 3, corresponding to the least significant bits. To extract field D, register 1 is shifted 12 bits to the left by instruction 5 so that field C is at the beginning of register 4 corresponding to the positions for the least significant bits. Then at instruction 6, all the bits except the bits corresponding to field D are masked so that only those bits remain in the positions corresponding to the least significant bits of register 4 and there is no need to mask any bits for the register formation in this example. It should be noted that the order of the shift and mask steps in instructions 5 and 6 are reversed from instructions 3 and 4 to show that it does not matter whether the software first masks then shifts or first shifts and then masks.
The software shift and mask technique described above generally requires execution of at least two instructions to extract each field. Often times, additional instructions are performed for each extracted field because extra bits are added when a modification is made to the format of the header, i.e., the standards for the header fields change. The additional instructions increase the time taken to extract each field and thereby slow the process.
The additional instructions typically comprise at least another read instruction. This is undesirable because a variable amount of time is needed to extract the fields. Also, a read instruction consumes more time than other processing instructions due to the time needed to access a memory which, in turn, adds an additional variable aspect to the field extraction process. Accordingly, even though software field extraction techniques are flexible and able to adapt to changing standards, there is a substantial cost associated with their use resulting from the increased and variable time of the software field extraction.
As the speed of network interfaces increases, the time budgeted for processing each data packet decreases. Presently, the processing time budgeted in high speed interfaces severely restricts the number of software instructions that can be performed to extract fields of the data packet header. When the budgeted time does not allow enough instructions to be executed for completing the extraction, the use of hardware must be maximized so that the operations performed on the data packets may be completed within the budgeted time.
In one known approach for extracting fields from a header, a synchronous hardware circuit is used. Here, bits corresponding to the desired fields are hardwired so that their contents are extracted directly by the hardware. As many fields as desired may be wired so that their bits are all extracted, preferably in one clock cycle. While this hardware solution extracts header bits at high speed, the known hardware mechanisms are not easily modified for evolving header standards since re-wiring must be performed for changes in the fields to be extracted.
As data transmission rates increase, traditional software data manipulation techniques for field extraction cannot guarantee completion within an allotted time. While conventional software field extraction techniques provide flexibility for extracting arbitrary information, known software techniques do not guarantee that all extractions will be performed in a fixed amount of time. As higher speed switches and interfaces are introduced, the extraction time budgeted for each data packet is reduced and a greater need arises for completing the extraction in a fixed amount of time. Also, conventional hardware techniques for field extraction do not provide the necessary flexibility to adapt to the changing standards for header fields. Accordingly, a solution to field extraction is desirable that allows high speed interfaces to be developed that can be readily modified to evolving standards of the header fields.